package com.hua.argi;

/**
 * @author: _hua
 * @created: 2019/3/26.
 * @updater:
 * @description:
 */
public class InsertSort {

    public static int[] sort(int[] array){
        //从1开始，0为已排序，未排序插入到已排序
        for(int i=1;i<array.length;i++){
           int temp =array[i];//记录要插入的数据
           int j=i;
           while (j>0&&temp<array[j-1]){//从已经排序的序列最右边的开始比较，找到比其小的数
               array[j]=array[j-1];
               j--;
           }
           array[j]=temp;//存在比其小的数，插入
        }
        return array;
    }

    //遍历显示数组
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args){
        int[] array = {4,2,8,9,5,7,6,1,3};
        //未排序数组顺序为
        System.out.println("未排序数组顺序为：");
        display(array);
        System.out.println("-----------------------");
        array = sort(array);
        System.out.println("-----------------------");
        System.out.println("经过插入排序后的数组顺序为：");
        display(array);
    }
}
